The main elements of networks for communicating sets of information data are network devices and communication links. The network devices include end-user devices and routers. Routers control the flow of data traffic in the network, between networks and between the network and the end-user devices. Basic information on routers and their use in networks is disclosed by Radia Perlman in the book entitled INTERCONNECTIONS, the second edition of which was published by Addison-Wesley in 1999.
Messages containing information are transmitted through the network in data sets known in the art by such names as packets, frames, cells and protocol data units. In this disclosure, the term packet will be used to describe such data sets. Each packet includes a header that includes a destination address. Each router has a number of channels through each of which the router receives messages from, and transmits messages to, the network device connected by a communication link to the channel. The router typically transmits messages onward through the network via a different channel from the one through which the messages were received.
The router channel to which a given message is sent for transmission is determined by the destination address in the headers of the packets in which the message is contained, and additionally from address information stored in an address table that forms part of the router. The address table is hierarchical and stores address information relating to the network or end-user device connected to each channel of the router. The address information is detailed with respect to the domains of end-user devices connected to the channels and is more general with respect to networks connected to the channels. Specifically, the address information indicates what is connected to each of the channels of the router. For example, the address information might indicate that a packet with a given destination address should be sent through the router to channel n for onward transmission. When the router determines the channel to which to send a packet, there is no guarantee that the channel is connected to a network device that is any closer to the destination of the packet than the router itself.
The conventional network architecture described above works well in many ways. However, it can be inefficient and can result in messages being delayed. Delays are undesirable, and are especially so in new applications such as video streaming and Voice over Internet. With the conventional routing scheme, messages may cross the continent several times and may pass through many routers before reaching their final destination. Before transmitting a message to another network device, each router may store all or part of the message for a storage time that depends on network traffic. The storage time may become very long as the network traffic approaches saturation. This increases the likelihood for messages to be delayed unacceptably, especially at times of high traffic.
Thus, what is needed is a network in which messages are transmitted to their destination by a route that is more direct that the route that typically results from the conventional routing scheme described above. A more direct routing can potentially reduce the number of routers that the message passes through on its way to its destination and, hence, the potential for the message being delayed.